package com.code;

/**
 * 描述:
 * 快排
 * @author luzhongfu
 * Created by lucky on 2019-09-18 1:48 PM
 */
public class QuickSort {

    private static int partition(int[] array, int start, int end){
        int i = start;
        int j = end;
        //取0位数组
        int buff = array[start];
        while (i < j){
            //
            while (i < j && array[j] >= buff){
                j --;
            }
            array[i] = array[j];
            while (i < j && array[i] <= buff){
                i ++;
            }
            array[j] = array[i];
        }
        array[i] = buff;
        return i;
    }

    private static void sort(int[] array, int start, int end){
        if(start < end){
            int partition = partition(array, start, end);
            sort(array,start,partition - 1);
            sort(array,partition + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] array = {9,10,11,4,5,8};
        sort(array,0,array.length - 1);
        for (int i = 0 ; i < array.length; i ++){
            System.out.print("-" + array[i]);
        }
    }
    /**
     * 9 10 11 4 5 8
     * j = 5
     * 8 10 11 4 5 x
     * i = 1
     * 8 x 11 4 5 10
     * j = 4
     *
     * 8 5 11 4 x 10
     * i = 2
     * 8 5 x 4 11 10
     * j = 3
     * 8 5 4 x 11 10
     * i = 3
     * 8 5 4 9 11 10
     *
     * //下面在排
     *
     * start 0 end 2
     * start 2 end 5
     *
     *
     *
     */
}
